package com.han.algo_ds.algorithm._01_07_compare_sort._01bubble_sort;

import org.junit.Test;

import com.han.algo_ds.algorithm._01_07_compare_sort.tools.Integers;
import com.han.algo_ds.algorithm._01_07_compare_sort.tools.Times;

/**
* @author hanpeng
* @version 创建时间：2020年7月29日 下午5:37:36
* @ClassName 类名称
* @Description 类描述
*/
public class BubbleSort {
	public static void main(String[] args) {
		Integer[] array1=Integers.random(10, 1, 10000);
		/*Integer[] array1={19 , 9, 16 , 7 , 26 , 25 , 11, 33, 41, 48 ,52};*/
		/*Integer[] array1= {4351,3904,2199,1972,2251,9166,5290,9489,3340,879};*/
		/*Integer[] array1= {772,9673,8224,2233,4784,3730,3800,3778,6670,2342};*/
		Integer[] array2 = Integers.copy(array1);
		Integer[] array3 = Integers.copy(array1);
		for (int i = 0; i < array1.length; i++) {
			System.out.print(array1[i]+"_");
			
		}
		System.out.println();
		Times.test("sort1", ()->{
			new BubbleSort().sort1(array1);
		});
		Times.test("sort2", ()->{
			new BubbleSort().sort2(array2);
		});
		Times.test("sort3", ()->{
			new BubbleSort().sort3(array3);
		});
		for (int i = 0; i < array1.length; i++) {
			System.out.print(array1[i]+"_");
		}
		System.out.println();
		
		for (int i = 0; i < array2.length; i++) {
			System.out.print(array2[i]+"_");
			
		}
		System.out.println();
		for (int i = 0; i < array3.length; i++) {
			System.out.print(array3[i]+"_");
			
		}
	}
	@Test
	public void sort1(Integer[] array) {
		for (int j = 0; j < array.length-1; j++) {  //有多少轮移动 i-1 最后一轮不用
			for (int i = 1; i < array.length-j; i++) {
				if(array[i]<array[i-1]) {
					int beforeValue = array[i-1];
					array[i-1]=array[i];
					array[i]=beforeValue;
				}
			}
		}
	}
	/**
	 * 冒泡排序的优化
	 * 如果序列已经完全有序，可以提前终止冒泡排序
	 */
	@Test
	public void sort2(Integer[] array) {
		for (int j = 0; j < array.length-1; j++) {  //有多少轮移动 i-1 最后一轮不用
			boolean sorted=true;
			for (int i = 1; i < array.length-j; i++) {
				if(array[i]<array[i-1]) {
					int beforeValue = array[i-1];
					array[i-1]=array[i];
					array[i]=beforeValue;
					sorted=false;
				}
			}
			if(sorted) {
				break;
			}
		}
	}
	/**
	 * @param array
	 * 果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
	 * 这时候不用进行任何一次交换 
	 * 比如最后又x 位 已经排好序了len-x+1
	 * 19 9 16 7 26 25 11 33 41 48 52
	 *                    -----------不需要排序了
	 * 772,9673,8224,2233,4784,3730,3800,3778,6670,2342
	 * 
	 * 第一轮        i=8
	 */
	@Test
	public void sort3(Integer[] array) {
		int end=array.length-1;
		//只需要排len-1次  想象力  
		for (int j = 0; j < end;) {  
			int sortedIndex=1;
			for (int i = 1; i <=end; i++) {
				if(array[i]<array[i-1]) {
					int beforeValue = array[i-1];
					array[i-1]=array[i];
					array[i]=beforeValue;
					sortedIndex=i;
				}
			}
			j=0;
			end=sortedIndex-1;
		}
	}
	@Test
	public void sort4(Integer[] array) {
		int end=array.length-1;
		//只需要排len-1次  想象力  
		for (; end>0;end--) {  
			int sortedIndex=1;
			for (int begin = 1; begin <=end; begin++) {
				if(array[begin]<array[begin-1]) {
					int beforeValue = array[begin-1];
					array[begin-1]=array[begin];
					array[begin]=beforeValue;
					sortedIndex=begin;
				}
			}
			end=sortedIndex;
		}
	}
	
}
